package org.example.Soution003;

public class DynamicProgrammingSquareNumber {
    public static void main(String[] args) {
        DynamicProgrammingSquareNumber obj=new DynamicProgrammingSquareNumber();
        System.out.println(obj.numSquares2(12));
    }

    public int numSquares(int n) {
        int[] minTimes=new int[n+1];
        for(int i=1;i<=n;i++){
            int minn=Integer.MAX_VALUE;
            for(int j=1;j*j<=i;j++){
                minn=Math.min(minn,minTimes[i-j*j]);
            }
            minTimes[i]=minn+1;
        }
        return minTimes[n];
    }

    public int numSquares2(int n) {
        if(isSquare(n)){
            return 1;
        }
        if(isFourNum(n)){
            return 4;
        }
        for(int i=1;i*i<=n;i++){
            if(isSquare(n-i*i)){
                return 2;
            }
        }
        return 3;
    }

    public boolean isSquare(int num){
        int y=(int)Math.sqrt(num);
        return y*y==num;
    }

    public boolean isFourNum(int num){
        //判断是否可以表示成 num=4^k*(8m+7)
        //先把4除空
        while(num%4==0){
            num=num/4;
        }
        //判断其除于8的余数是不是7
        return num%8==7;
    }
}
